/**
 * $Id: dataset.h 8 2012-06-28 09:25:09Z haifeng.813@gmail.com $
 *
 * @author Liu Haifeng
 * @description Define list, map data structure and related operations.
 *
 */

#ifndef _DATA_SET_H
#define _DATA_SET_H

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <defs.h>

/**********************************************************
 *             List structure and operations              *
 **********************************************************/

/**
 * List node structure.
 */
typedef struct st_list_node {
	void * pData;
	struct st_list_node * pPrev;
	struct st_list_node * pNext;
} _list_node;

/**
 * List structure.
 */
typedef struct st_list {
	struct st_list_node head;
	struct st_list_node tail;
	struct st_list_node * pCurrent;
	unsigned int size;
} list;

/**
 * Create a list data structure.
 */
static list * create_list() {
	list * pList = (list*) awl_alloc(sizeof(list));
	pList->head.pData = NULL;
	pList->head.pPrev = NULL;
	pList->head.pNext = &pList->tail;
	pList->tail.pData = NULL;
	pList->tail.pPrev = &pList->head;
	pList->tail.pNext = NULL;
	pList->pCurrent = &pList->head;
	pList->size = 0;
	return pList;
}

/**
 * Get total size of the list.
 */
static unsigned int count_list(list * pList) {
	if (pList == NULL)
		return 0;
	return pList->size;
}

static _list_node * _seek_node(list * pList, unsigned int pos) {
	_list_node * pNode = pList->head.pNext;
	unsigned int i;
	for (i = 0; i < pos && pNode != &pList->tail; i++) {
		pNode = pNode->pNext;
	}
	return pNode == &pList->tail ? NULL : pNode;
}

static inline void _link_node(_list_node * pPrev, _list_node * pNext) {
	if (pPrev != NULL)
		pPrev->pNext = pNext;
	if (pNext != NULL)
		pNext->pPrev = pPrev;
}

static _list_node * _create_node(void * pData, _list_node * pPrev,
		_list_node * pNext) {
	_list_node * pNewNode = (_list_node*) awl_alloc(sizeof(_list_node));
	pNewNode->pData = pData;
	_link_node(pPrev, pNewNode);
	_link_node(pNewNode, pNext);
	return pNewNode;
}

static _list_node * _contains(list * pList, void * pData,
		int (*compare)(void *, void *)) {
	if (pList == NULL)
		return NULL;
	_list_node * pNode = pList->head.pNext;
	while (pNode != &pList->tail) {
		if (compare(pData, pNode->pData) == 0)
			return pNode;
		pNode = pNode->pNext;
	}
	return NULL;
}

/**
 * Whether the list contains the given data.
 */
static int contains(list * pList, void * pData,
		int (*compare)(void *, void *)) {
	_list_node * pNode = _contains(pList, pData, compare);
	return pNode != NULL;
}

static int _insert(list * pList, _list_node * pRef, void * pData) {
	if (pRef == NULL)
		pRef = &pList->tail;
	else if (pRef == &pList->head)
		pRef = pRef->pNext;
	_list_node * pNewNode = _create_node(pData, pRef->pPrev, pRef);
	if (pNewNode == NULL)
		return FALSE;
	pList->size++;
	return TRUE;
}

static int _insert_all(list * pList, _list_node * pRef, list * pOtherList) {
	if (pRef == NULL)
		pRef = &pList->tail;
	else if (pRef == &pList->head)
		pRef = pRef->pNext;
	_list_node * pNewNode = pOtherList->head.pNext;
	while (pNewNode != &pOtherList->tail) {
		_list_node * pRetNode = _create_node(pNewNode->pData, pRef->pPrev,
				pRef);
		if (pRetNode != NULL)
			pList->size++;
		pNewNode = pNewNode->pNext;
	}
	return TRUE;
}

/**
 * Insert a node to the give position of the specified list.
 */
static int insert(list * pList, unsigned int pos, void * pData) {
	return _insert(pList, _seek_node(pList, pos), pData);
}

/**
 * Insert all nodes in the given list to the specified position of the list.
 */
static int insert_all(list * pList, unsigned int pos, list * pOtherList) {
	return _insert_all(pList, _seek_node(pList, pos), pOtherList);
}

static int insert_current(list * pList, void * pData) {
	return _insert(pList, pList->pCurrent, pData);
}

static int insert_all_current(list * pList, list * pOtherList) {
	return _insert_all(pList, pList->pCurrent, pOtherList);
}

static inline void _remove_node(list * pList, _list_node * pNode) {
	_link_node(pNode->pPrev, pNode->pNext);
	awl_free(pNode);
	pList->size--;
}

/**
 * Remove the node at the given position of the list.
 */
static void * remove_pos(list * pList, unsigned int pos) {
	_list_node * pNode = _seek_node(pList, pos);
	if (pNode == NULL)
		return NULL;
	void * pData = pNode->pData;
	if (pList->pCurrent == pNode)
		pList->pCurrent = pNode->pNext;
	_remove_node(pList, pNode);
	return pData;
}

/**
 * Remove the node contains the given data.
 */
static void * remove_data(list * pList, void * pData,
		int (*compare)(void *, void *)) {
	_list_node * pNode = _contains(pList, pData, compare);
	if (pNode == NULL)
		return NULL;
	void * pOldData = pNode->pData;
	_remove_node(pList, pNode);
	return pOldData;
}

/**
 * Get the node at the given position of the list.
 */
static void * at(list * pList, unsigned int pos) {
	_list_node * pNode = _seek_node(pList, pos);
	return pNode == NULL ? NULL : pNode->pData;
}

/**
 * Get the head node.
 */
static void * head(list * pList) {
	return pList->head.pNext == &pList->tail ? NULL : pList->head.pNext->pData;
}

/**
 * Get the tail node.
 */
static void * tail(list * pList) {
	return pList->tail.pPrev == &pList->head ? NULL : pList->tail.pPrev->pData;
}

/**
 * Add a node to the tail
 */
static int push(list * pList, void * pData) {
	_list_node * pNewNode = _create_node(pData, pList->tail.pPrev,
			&pList->tail);
	if (pNewNode == NULL)
		return FALSE;
	pList->size++;
	return TRUE;
}

/**
 * Add all nodes in the given list to the tail
 */
static int push_all(list * pList, list * pOtherList) {
	_list_node * pNode = pOtherList->head.pNext;
	while (pNode != &pOtherList->tail) {
		_list_node * pRetNode = _create_node(pNode->pData, pList->tail.pPrev,
				&pList->tail);
		if (pRetNode != NULL)
			pList->size++;
		pNode = pNode->pNext;
	}
	return TRUE;
}

/**
 * remove and return the tail node.
 */
static void * pop(list * pList) {
	_list_node * pNode = pList->tail.pPrev;
	if (pNode == &pList->head)
		return NULL;
	void * pData = pNode->pData;
	if (pList->pCurrent == pNode)
		pList->pCurrent = &pList->tail;
	_remove_node(pList, pNode);
	return pData;
}

/**
 * remove and return the head node.
 */
static void * launch(list * pList) {
	_list_node * pNode = pList->head.pNext;
	if (pNode == &pList->tail)
		return NULL;
	void * pData = pNode->pData;
	if (pList->pCurrent == pNode)
		pList->pCurrent = pNode->pNext;
	_remove_node(pList, pNode);
	return pData;
}

/**
 * Move the current pointer to the head node.
 */
static void move_head(list * pList) {
	pList->pCurrent = &pList->head;
}

/**
 * Move the current pointer to the end node.
 */
static void move_tail(list * pList) {
	pList->pCurrent = &pList->tail;
}

/**
 * Get previous node.
 */
static void * prev(list * pList) {
	if (pList->pCurrent == &pList->head)
		return NULL;
	pList->pCurrent = pList->pCurrent->pPrev;
	return pList->pCurrent == &pList->head ? NULL : pList->pCurrent->pData;
}

static void * current(list *pList) {
	return pList->pCurrent == &pList->head ? NULL :
			pList->pCurrent == &pList->tail ? NULL : pList->pCurrent->pData;
}

/**
 * Get next node.
 */
static void * next(list * pList) {
	if (pList->pCurrent == &pList->tail)
		return NULL;
	pList->pCurrent = pList->pCurrent->pNext;
	return pList->pCurrent == &pList->tail ? NULL : pList->pCurrent->pData;
}

static inline void _swap(void ** d1, void ** d2) {
	void * d = *d1;
	*d1 = *d2;
	*d2 = d;
}

static void _quick_sort(void ** arr, unsigned int left, unsigned int right,
		int (*compare)(void * d1, void * d2)) {
	if (left >= right)
		return;
	unsigned int l = left, r = right;
	void * povit = arr[(left + right) / 2];
	while (l != r) {
		while (compare(arr[l], povit) < 0)
			l++;
		while (compare(arr[r], povit) > 0)
			r--;
		if (l != r) {
			if (compare(arr[l], arr[r]) == 0) {
				l++;
				continue;
			}
			_swap(&arr[l], &arr[r]);
		}
	}
	if (l > 0 && left < l - 1)
		_quick_sort(arr, left, l - 1, compare);
	if (right > l + 1)
		_quick_sort(arr, l + 1, right, compare);
}

/**
 * Sort list nodes
 */
static list * sort(list * pList, int (*compare)(void *, void *)) {
	const unsigned int count = count_list(pList);
	if (count < 1)
		return pList;
	void ** arr = (void **) awl_alloc(sizeof(void *) * count);
	_list_node * pNode = pList->head.pNext;
	unsigned int i;
	for (i = 0; i < count; i++) {
		arr[i] = pNode->pData;
		pNode = pNode->pNext;
	}
	// quick sort
	_quick_sort(arr, 0, count - 1, compare);
	pNode = pList->head.pNext;
	for (i = 0; i < count; i++) {
		pNode->pData = arr[i];
		pNode = pNode->pNext;
	}
	awl_free(arr);
	return pList;
}

/**
 * Get sub list
 */
static list * sub_list(list * pList, unsigned int start, unsigned int end) {
	if (pList == NULL || start > end)
		return NULL;
	_list_node * pNode = pList->head.pNext;
	unsigned int i;
	for (i = 0; i != start && pNode != &pList->tail; i++) {
		pNode = pNode->pNext;
	}
	if (pNode == &pList->tail)
		return NULL;
	list * pNewList = create_list();
	for (; i < end && pNode != &pList->tail; i++) {
		push(pNewList, pNode->pData);
		pNode = pNode->pNext;
	}
	return pNewList;
}

static void clear_list(list * pList) {
	while (pList->size > 0)
		pop(pList);
}

/**
 * Destroy the list structure.
 */
static void destroy_list(list * pList) {
	_list_node * pNode = pList->head.pNext;
	_list_node * pDelNode = NULL;
	while (pNode != &pList->tail) {
		pDelNode = pNode;
		pNode = pNode->pNext;
		awl_free(pDelNode);
	}
	awl_free(pList);
}

/**********************************************************
 *                  Map structure and operations                                                    *
 **********************************************************/

typedef struct st_map_entry {
	const char * key;
	void * pData;
} map_entry;

#define DEF_MAP_CAPACITY (64)
#define DEF_MAP_LOAD_FACTOR (0.75)

typedef struct st_map {
	unsigned int capacity;
	list ** hash_table;
	unsigned int size;
} map;

static map * create_map(unsigned int initial_capacity) {
	map * pMap = (map *) awl_alloc(sizeof(map));
	if (initial_capacity == 0) {
		pMap->capacity = DEF_MAP_CAPACITY;
	} else {
		pMap->capacity = 1;
		while (pMap->capacity < initial_capacity)
			pMap->capacity = pMap->capacity << 1;
	}
	pMap->hash_table = (list **) awl_alloc(sizeof(list *) * pMap->capacity);
	memset(pMap->hash_table, 0, sizeof(list *) * pMap->capacity);
	pMap->size = 0;
	return pMap;
}

static unsigned int count_map(map * pMap) {
	if (pMap == NULL)
		return 0;
	return pMap->size;
}

static int _hash(const char * str) {
	if (str == NULL)
		return 0;
	int hash = 0;
	unsigned int i = 0;
	while (str[i] != '\0') {
		hash = hash * 31 + str[i++];
	}
	return hash;
}

static inline unsigned int _index_for(map * pMap, const char * key) {
	return _hash(key) & (pMap->capacity - 1);
}

static int _compare_str(const char * s1, const char * s2) {
	if (s1 == NULL && s2 == NULL)
		return 0;
	else if (s1 == NULL)
		return -1;
	else if (s2 == NULL)
		return 1;
	unsigned int i = 0;
	while (s1[i] == s2[i] && s1[i] != '\0' && s2[i] != '\0')
		i++;
	if (s1[i] == s2[i])
		return 0;
	else if (s1[i] > s2[i])
		return 1;
	else
		return -1;
}

static void _destroy_map_entry(map_entry * pEntry) {
	awl_free((char *) pEntry->key);
	awl_free(pEntry);
}

/**
 * put a new key-value pair. if the key exists, return old value, else return NULL.
 */
static void * put(map * pMap, const char * key, void * pData);

static void _resize(map * pMap) {
	unsigned int old_capacity = pMap->capacity;
	list ** old_hash_table = pMap->hash_table;
	pMap->capacity = pMap->capacity << 1;
	pMap->hash_table = (list **) awl_alloc(sizeof(list *) * pMap->capacity);
	memset(pMap->hash_table, 0, sizeof(list *) * pMap->capacity);
	pMap->size = 0;
	unsigned int i;
	for (i = 0; i < old_capacity; i++) {
		list * pEntries = old_hash_table[i];
		if (pEntries == NULL)
			continue;
		move_head(pEntries);
		map_entry * pEntry = NULL;
		while ((pEntry = (map_entry *) next(pEntries)) != NULL) {
			assert(put(pMap, pEntry->key, pEntry->pData) == NULL);
			_destroy_map_entry(pEntry);
		}
		destroy_list(pEntries);
	}
	awl_free(old_hash_table);
}

static char * _clone_str(const char * str) {
	char * s = (char *) awl_alloc(sizeof(char) * strlen(str) + 1);
	memset(s, 0, sizeof(char) * strlen(str) + 1);
	strcpy(s, str);
	return s;
}

/**
 * put a new key-value pair. if the key exists, return old value, else return NULL.
 */
static void *put(map * pMap, const char * key, void * pData) {
	if (pMap->size >= pMap->capacity * DEF_MAP_LOAD_FACTOR) {
		_resize(pMap);
	}
	unsigned int index = _index_for(pMap, key);
	list * pEntries = pMap->hash_table[index];
	if (pEntries == NULL) {
		pEntries = create_list();
		pMap->hash_table[index] = pEntries;
	}
	_list_node * pNode = pEntries->head.pNext;
	while (pNode != &pEntries->tail) {
		if (_compare_str(key, ((map_entry *) pNode->pData)->key) == 0) {
			void *pOldData = ((map_entry *) pNode->pData)->pData;
			((map_entry *) pNode->pData)->pData = pData;
			return pOldData;
		}
		pNode = pNode->pNext;
	}
	map_entry * pEntry = (map_entry *) awl_alloc(sizeof(map_entry));
	pEntry->key = _clone_str(key);
	pEntry->pData = pData;
	push(pEntries, pEntry);
	pMap->size++;
	return NULL;
}

static void * get(map * pMap, const char * key) {
	unsigned int index = _index_for(pMap, key);
	list * pEntries = pMap->hash_table[index];
	if (pEntries == NULL)
		return NULL;
	_list_node * pNode = pEntries->head.pNext;
	while (pNode != &pEntries->tail) {
		if (_compare_str(key, ((map_entry *) pNode->pData)->key) == 0)
			return ((map_entry*) pNode->pData)->pData;
		pNode = pNode->pNext;
	}
	return NULL;
}

static void * remove_entry(map * pMap, const char * key) {
	int index = _index_for(pMap, key);
	list * pEntries = pMap->hash_table[index];
	if (pEntries == NULL)
		return NULL;
	_list_node * pNode = pEntries->head.pNext;
	while (pNode != &pEntries->tail
			&& _compare_str(key, ((map_entry *) pNode->pData)->key) != 0) {
		pNode = pNode->pNext;
	}
	if (pNode == &pEntries->tail)
		return NULL;
	map_entry * pEntry = (map_entry *) pNode->pData;
	void * pData = pEntry->pData;
	_destroy_map_entry(pEntry);
	_remove_node(pEntries, pNode);
	pMap->size--;
	return pData;
}

static list * all_entries(map * pMap) {
	list * pAllEntries = create_list();
	unsigned int i;
	for (i = 0; i < pMap->capacity; i++) {
		list * pEntries = pMap->hash_table[i];
		if (pEntries != NULL)
			push_all(pAllEntries, pEntries);
	}
	return pAllEntries;
}

static void clear_map(map * pMap) {
	list ** hash_table = pMap->hash_table;
	unsigned int i;
	for (i = 0; i < pMap->capacity; i++) {
		list * pList = hash_table[i];
		if (pList != NULL) {
			move_head(pList);
			map_entry * pEntry = NULL;
			while ((pEntry = (map_entry*) next(pList)) != NULL) {
				_destroy_map_entry(pEntry);
			}
			clear_list(hash_table[i]);
		}
	}
	pMap->size = 0;
}

static void destroy_map(map * pMap) {
	if (pMap == NULL)
		return;

	unsigned int i;
	for (i = 0; i < pMap->capacity; i++) {
		list * pEntries = pMap->hash_table[i];
		if (pEntries != NULL) {
			_list_node * pNode = pEntries->head.pNext;
			while (pNode != &pEntries->tail) {
				_destroy_map_entry((map_entry *) pNode->pData);
				pNode = pNode->pNext;
			}
			destroy_list(pEntries);
		}
	}
	awl_free(pMap->hash_table);
	awl_free(pMap);
}

#endif /* end of _DATA_SET_H */
